package offerbook.Code25_pathInBT;

import utils.TreeNode;

import java.util.Stack;

/**
 * 给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，
 * 这条路径上所有节点值相加等于目标和。【leetcode112】
 * @date 2020/3/9 19:08
 */
public class Code04_FindSumInAllPath1_leetcode112 {
    //递归
    private boolean process(TreeNode root, int sum){
        if(root == null) return false;
        sum -= root.val;
        if(root.left == null && root.right == null && sum == 0) return true;
        return process(root.left,sum) || process(root.right,sum);
    }
    //迭代。多加一个栈，用来记录当前路径的已有的和
    private boolean process2(TreeNode root,int sum){
        if(root == null) return false;
        Stack<TreeNode> node_stack = new Stack<>();
        Stack<Integer> sum_stack = new Stack<>();
        node_stack.push(root);
        sum_stack.push(sum - root.val);

        int curr_sum;
        while (!node_stack.isEmpty() ) {
            //pre-order,process
            root = node_stack.pop();
            curr_sum = sum_stack.pop();
            //对于当前node有两种选择，左右两个分支
            if ((root.right == null) && (root.left == null) && (curr_sum == 0))
                return true;

            if (root.right != null) {
                node_stack.add(root.right);
                sum_stack.add(curr_sum - root.right.val);
            }
            if (root.left != null) {
                node_stack.add(root.left);
                sum_stack.add(curr_sum - root.left.val);
            }
        }
        return false;
    }

}
